代码优化的目标是在编译时发现有关程序运行时行为的信息，并利用该信息来改进代码。

代码优化的引入

以访问数组为例子，对于数组a[m][n]，每个元素占$s$字节。一般来讲，访问数组元素a[i][j]需要计算： $$ a+ins+j*s $$ 如果我们不知道任何上下文信息，只知道这是一个对数组元素的访问，那么完整地计算整个表达式是必不可少的。

但是，如果我们知道一些上下文，比如说，这是一个对数组的依次遍历，我们就有机会减少每次访问数组元素的工作量。

// 假设对数组的访问形式
for (int i=0;i<m;++i) {
    for (int j=0;j<n;++j) {
        a[i][j];
    }
}

我们的目标是尽可能减少最内层循环访问数组的工作量。首先我们注意到访问每次都要计算j*s。所以我们可以将内层循环的步长改为$s$来减少一次乘法计算：

for (int i=0;i<m;++i) {
    for (int j'=0;j'<n*s;j'+=s) {
        // a[i][j]的地址：
        (void*)a+i*n*s+j'
    }
}

同样的，我们可以对i也这么干，减少两次乘法：

for (int i'=0;i'<m*n*s;i'+=n*s) {
    for (int j'=0;j'<n*s;j'=j'+s) {
        // a[i][j]的地址：
        (void*)a+i'+j'
    }
}

这称为运算符强度削减（OSR），即将一系列操作重写为等价操作，但运算符的强度/代价下降。我们极大减少了内层循环的代价，而几乎没有引入其他代价。（在循环语句中的乘法实际上只用计算一次，甚至直接由编译器在编译时计算）。

有没有办法让加法也去掉呢，当然是有的：

for (void* a'=a;a'<a+m*n*s;a'+=n*s) {
    for (void* b'=a';b'<a'+n*s;b'+=s) {
        // a[i][j]的地址：
        b;
    }
}

我们利用上下文信息将操作序列转换为等价形式，同时大大降低了计算量。这就是代码优化的力量。

代码优化的类型

按代码优化的考察范围来分类，大致可以将代码优化分为四种： 1. 局部优化 局部优化以BB（Basic Block）为范围。BB是一串在执行时一定被线性执行的指令，且只有一个入口和一个出口。局部优化的范围很小，但是拥有最确定的控制流信息。 2. 区域优化 区域优化的范围大于BB，但小于一个过程。针对循环体的优化就是典型的区域优化。 3. 过程内优化 过程内优化将整个过程作为上下文。 4. 过程间优化 过程间优化也称为全程序优化。它将整个程序作为上下文。

下面以具体的例子讲解各种优化类型：

局部优化

LVN（局部值编号）优化可以用于发现代码中的冗余计算。如：

a=b+c
b=a-d
c=b+c
d=a-d

这里面最后一条赋值语句中计算a-d是冗余的。

为了发现这样的冗余计算，一个自然的想法是将有相同结果的表达式标识出来，然后就可以用简单的表达式替换复杂的表达式。（如上面就可以用b来代替a-d）。为表达式编号可以实现这一点。两个表达式$e_1,e_2$有相同的编号，当且仅当在给定的上下文中e_1=e_2。比如，我们可以为a,b+c编号为1，为b和a-d编号为2，因为c和b+c值一样，所以c编号也为1。因为d=a-d的右边编号为2，所以可以使用任意编号为2的表达式替换a-d。

可是，问题并没有那么轻松地被解决。考虑下面的赋值串：

a=x+y
b=x+y
a=17
c=x+y

很显然，第2和第4条语句中右边的计算都是冗余的。我们当然可以为a,b,x+y都编号为1。但当处理到a=17时，应该给a编号为多少呢？也许将a以前的编号抹除，换成新编号2是个好主意。当然可以！毕竟bb是一条线性序列。但是有更优雅的做法。出现问题的本质原因是在计算的过程中变量a被重新赋值。假如我们禁止变量被重新赋值，并且把原来的变量重新赋值视为定义一个完全不同的变量。一切都迎刃而解。这就是大名鼎鼎的SSA（静态单赋值）。

a0=x+y
b=x+y
a1=17
c=x+y

现在我们知道，可以用a0或者b来代替x+y。

LVN的概念已经全部介绍完，下面是一种简单的实现方式。

用散列表来存储每个表达式的编号。在遇见一个表达式t=l op r时，算法查找l和r的编号，如果找到编号，则直接使用，否则创建新表项并分配新编号。假设l和r的编号是$v(l)$和$v(r)$，算法接下来以v(l) op v(r)$为键（注意不是l op r`，这是因为算法只关心值而不关心值是否由同一对计算出来的）进行查找，如果找到找到编号，则直接使用，否则创建新表项并分配新编号。

总之，区域优化利用了bb是一个线性序列的性质，可以通过一次扫描实现。同时也是最简单的优化。

区域优化

区域优化针对多个bb。下面以超局部值编号和循环展开为例子。

超局部值编号

可以将局部值编号拓展到EBB上。EBB是一组构成树结构的bb。EBB有一个很好的性质。即从根bb开始到其中任何一个bb形成的链，都可以视为一个bb。

如果暴力地直接将这样的链视为bb然后运行LVN，是可以的。但是会有一些bb被重复处理。为了优化算法效率，我们要想办法复用这些bb的信息。

通过为每个bb的分析结果指定一个作用域。在进入bb时增加一层作用域，在退出bb时消除作用域，就可以高效地复用信息。

循环展开

循环展开将一个循环体复制几份，一次迭代就可以执行几次循环体。循环展开有利可图的点在于它可以减少循环判断和分支的次数。

一个最简单的循环展开如下：

for (int i = 0;i<n;++i) {
    sum++;
}

// 按4展开

int netra = n % 4;
if (netra > 0) {
    for (int i = 0;i<netra;++i) {
        sum++;
    }
}
for (int i = netra;i<n;i+=4) {
    sum++;
    sum++;
    sum++;
    sum++;
}

循环展开需要一个小小的启动循环，以保证循环次数是4的倍数。若循环次数在编译时可确定，编译器才能判断是否需要启动循环。

当然，可以展开内层循环或者外层循环。

for (int i = 0;i<m;++i) {
    for (int j = 0;j<n;++j) {
        sum++;
    }
}

// 展开内层
for (int i = 0;i<m;++i) {
    int netra = n % 4;
    if (netra > 0) {
        for (int i = 0;i<netra;++i) {
            sum++;
        }
    }
    for (int i = netra;i<n;i+=4) {
        sum++;
        sum++;
        sum++;
        sum++;
    }
}

// 展开外层
int mextra = m % 4;
if (mextra > 0) {
    for (int i = 0;i<mextra;++i) {
        for (int j = 0;j<n;++j) {
            sum++;
        }
    }
}

for (int i = mextra;i<m;++i) {
    for (int j = 0;j<n;++j) {
        sum++;
    }
    for (int j = 0;j<n;++j) {
        sum++;
    }
    for (int j = 0;j<n;++j) {
        sum++;
    }
    for (int j = 0;j<n;++j) {
        sum++;
    }
}

展开外层循环会得到几个内层循环。我们可以融合这些内层循环。展开外层循环并融合内层循环称为展开-轧挤(unroll-and-jam)。

最后得到融合的内层循环：

for (int i = mextra;i<m;++i) {
    for (int j = 0;j<n;++j) {
        sum++;
        sum++;
        sum++;
        sum++;
    }
}